BGP is an exterior gateway routing protocol in form of distance vectors, which is mainly used for distributing routing information among autonomous systems (AS). BGP is the core routing protocol for Internet at present, and is a de facto standard for exterior gateway routing protocols. Although BGP is a distance vector routing protocol, it uses incremental and triggered routing updates, instead of periodical updates across the whole routing table used in common distance vector routing protocols, which saves bandwidth occupancy for update.
Update information, including the prefix information, the withdrawn prefix information, the path attributes and so on, is exchanged among ASs via BGP. One important path attribute is the information regarding the AS paths (AS_PATH) through which the BGP update information passes to reach a network. Checking AS_PATH may prevent the occurrence of loop.
In current BGP protocols, there is no mechanism to verify the authenticity of the prefix and the AS_PATH, and thus announcement of illegal prefixes may occur due to wrong system configurations or malicious neighbor attacks. These might lead to attacks, such as routing hole, Denial of Service (DoS) and so on. Meanwhile, any malicious AS along the way might modify the AS_PATH, so that the propagation path for the update message cannot be determined. These are the main security vulnerabilities in BGP.
To solve the above security issues, two extended BGP framework schemes are proposed, that is, Secure Origin BGP (SOBGP) and Secure BGP (SBGP). Similar schemes are used for prefix verification in the two frameworks. By reference to SBGP, detailed descriptions are made below to the prefix verification in the two extended BGP framework schemes.
In SBGP, to verify the prefix information, a prefix owner, such as the top Internet Assigned Numbers Authority (IANA), a Regional Internet Registry (RIR) or an Internet Service Provider (ISP), distributes a certificate on the SBGP routers and authorizes a specific AS with a signature generated by the private key corresponding to the public key in the certificate so that the AS may announce the prefix it owns. The data object of the private key signature is also referred to as Address Attestation (AA), which is the correspondence between the prefix and the number for the AS generating the prefix. The AA information is also distributed among SBGP routers. Upon receipt of an update message, the recipient performs prefix verification according to the AA, that is, checks whether there is a corresponding relationship between the prefix and the AS generating the prefix in the AA. Only if the verification is successful, the recipient trusts the received prefix information. If the verification is unsuccessful, a process is performed according to local configurations, for example, discarding the update message or postponing the verification and so on.
Two different verification methods are applied for verification of the AS_PATH in SBGP and SoBGP, which are described blow.
In SoBGP, verification of AS_PATH is as follows. ASs supporting SoBGP deliver information about their directly connected AS to each other. Each AS collects the received connection information to generate topology for AS interconnections. Upon receipt of an update message, the AS checks whether the AS_PATH is a path present in the topology. If the AS_PATH is a path present in the topology, the verification is successful; otherwise, if the AS_PATH is not a path present in the topology, a process is performed according to local configurations, for example, discarding the update message or postponing the verification and so on.
When such an SoBGP system verifies AS_PATH with this method, it is only possible to confirm the presence of the AS_PATH, and it is impossible to verify whether the ASs in the AS_PATH are legal, which leads to a lower security for the SoBGP system.
In SBGP, verification of AS_PATH is as follows. During delivery of an update message, an AS signs the update message with a private key in a nested way, that is, the signed information comprises the signed portion of a preceding AS in addition to the content of the update message. Upon receipt of the update message, a public key is used to check layer by layer whether the signatures are legal. For example, when an update message reaches the Nth AS (N>2), the AS verifies the signature of the (N−1)th AS. If the verification is successful, a further verification is performed on the signature of the (N−2)th AS, and so on, until the verification for the signature of the first AS is successful. Accordingly, the verification for the AS_PATH is successful, and the received AS_PATH is trusted. This attests that the update message passes each AS in the AS_PATH. Then, the update message and the signatures of the preceding ASs are signed. After other verifications are successful, the update message is sent to the (N+1)th AS. If the verification is unsuccessful, a process is performed according to local configurations, for example, discarding the update message or postponing the verification and so on. With this method for verification of the AS_PATH, verification may be made as to whether each AS in the AS_PATH is legal. Only when all ASs in the AS_PATH are legal ASs to receive the update message, the received AS_PATH is trusted.
During verification of the AS_PATH with the above SBGP approach, all signatures in the nested signatures have to be verified. If a signature of the update message is signed by AS1, N−1 verifications are needed; if it is signed by the second AS, N−2 verifications are needed; and so on. When N is large, the time of iterative verifications becomes larger and larger. Key computation steps which require CPU dense operations, will be executed many times for a verification, which causes a very large burden on the CPU of a device. Because one important measure for BGP is the network convergence speed, large occupancy of CPU resources may impose a serious impact on the routing computation in the case of SBGP, which makes the SBGP technique infeasible.
Furthermore, similar problems also exist for SoBGP and SGBP during verification of the prefix. Because each AS has to perform prefix verification, large CPU resources are occupied and the load on CPU is increased.